Search Results

Documents authored by Jukna, Stasys

Document
DOI: 10.4230/LIPIcs.STACS.2019.41
Lower Bounds for DeMorgan Circuits of Bounded Negation Width

Authors: Stasys Jukna and Andrzej Lingas

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We consider Boolean circuits over {or, and, neg} with negations applied only to input variables. To measure the "amount of negation" in such circuits, we introduce the concept of their "negation width". In particular, a circuit computing a monotone Boolean function f(x_1,...,x_n) has negation width w if no nonzero term produced (purely syntactically) by the circuit contains more than w distinct negated variables. Circuits of negation width w=0 are equivalent to monotone Boolean circuits, while those of negation width w=n have no restrictions. Our motivation is that already circuits of moderate negation width w=n^{epsilon} for an arbitrarily small constant epsilon>0 can be even exponentially stronger than monotone circuits. We show that the size of any circuit of negation width w computing f is roughly at least the minimum size of a monotone circuit computing f divided by K=min{w^m,m^w}, where m is the maximum length of a prime implicant of f. We also show that the depth of any circuit of negation width w computing f is roughly at least the minimum depth of a monotone circuit computing f minus log K. Finally, we show that formulas of bounded negation width can be balanced to achieve a logarithmic (in their size) depth without increasing their negation width.
Cite as

Stasys Jukna and Andrzej Lingas. Lower Bounds for DeMorgan Circuits of Bounded Negation Width. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jukna_et_al:LIPIcs.STACS.2019.41,
  author =	{Jukna, Stasys and Lingas, Andrzej},
  title =	{{Lower Bounds for DeMorgan Circuits of Bounded Negation Width}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.41},
  URN =		{urn:nbn:de:0030-drops-102801},
  doi =		{10.4230/LIPIcs.STACS.2019.41},
  annote =	{Keywords: Boolean circuits, monotone circuits, lower bounds}
}
Document
DOI: 10.4230/DagSemProc.06111.8
Graphs and Circuits: Some Further Remarks

Authors: Stasys Jukna

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We consider the power of single level circuits in the context of graph complexity. We first prove that the single level conjecture fails for fanin-$2$ circuits over the basis ${oplus,land,1}$. This shows that the (surpisingly tight) phenomenon, established by Mirwald and Schnorr (1992) for quadratic functions, has no analogon for graphs. We then show that the single level conjecture fails for unbounded fanin circuits over ${lor,land,1}$. This partially answers the question of Pudl'ak, R"odl and Savick'y (1986). We also prove that $Sigma_2 eq Pi_2$ in a restricted version of the hierarhy of communication complexity classes introduced by Babai, Frankl and Simon (1986). Further, we show that even depth-$2$ circuits are surprisingly powerful: every bipartite $n imes n$ graph of maximum degree $Delta$ can be represented by a monotone CNF with $O(Deltalog n)$ clauses. We also discuss a relation between graphs and $ACC$-circuits.
Cite as

Stasys Jukna. Graphs and Circuits: Some Further Remarks. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{jukna:DagSemProc.06111.8,
  author =	{Jukna, Stasys},
  title =	{{Graphs and Circuits: Some Further Remarks}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.8},
  URN =		{urn:nbn:de:0030-drops-6218},
  doi =		{10.4230/DagSemProc.06111.8},
  annote =	{Keywords: Graph complexity, single level conjecture, Sylvester graphs, communication complexity, ACC-circuits}
}
Document
DOI: 10.4230/DagSemProc.06111.22
Very Large Cliques are Easy to Detect

Authors: Alexander E. Andreev and Stasys Jukna

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
It is known that, for every constant $kgeq 3$, the presence of a $k$-clique (a complete subgraph on $k$ vertices) in an $n$-vertex graph cannot be detected by a monotone boolean circuit using fewer than $Omega((n/log n)^k)$ gates. We show that, for every constant $k$, the presence of an $(n-k)$-clique in an $n$-vertex graph can be detected by a monotone circuit using only $O(n^2log n)$ gates. Moreover, if we allow unbounded fanin, then $O(log n)$ gates are enough.
Cite as

Alexander E. Andreev and Stasys Jukna. Very Large Cliques are Easy to Detect. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:DagSemProc.06111.22,
  author =	{Andreev, Alexander E. and Jukna, Stasys},
  title =	{{Very Large Cliques are Easy to Detect}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.22},
  URN =		{urn:nbn:de:0030-drops-6092},
  doi =		{10.4230/DagSemProc.06111.22},
  annote =	{Keywords: Clique function, monotone circuits, perfect hashing}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact